package JZOffer;

import java.util.HashMap;

/**
 * @author Lw中
 * @date 2021/9/26 21:49
 */
public class Jz07 {

    // Jz07.重建二叉树
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }

    }

    HashMap<Integer, Integer> map = new HashMap<>(); //标记中序遍历
    int[] preorder; // 保留的先序遍历，方便递归时依据索引查看先序遍历的值

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 方法一：使用递归性质的分治算法
        // 保留的先序遍历的二叉树
        this.preorder = preorder;
        //将中序遍历的值以及索引放在map中，方便递归获取左子树以及右子树的数量及其根的索引
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        // 三个索引分别为：当前根的索引，递归树的左边界，即数组左边界，递归树的右边界，即数组的右边界
        return recur(0, 0, inorder.length - 1);
    }

    /**
     * LWZ TODO : 2021/9/26 递归部分有点理解不透彻
     *
     */
    private TreeNode recur(int pre_root, int in_left, int in_right) {
        if (in_left > in_right) return null; // 递归终止条件
        TreeNode root = new TreeNode(preorder[pre_root]); //获取root节点
        int inorderIndex = map.get(preorder[pre_root]); //获取中序遍历中头节点的索引，方便获取左子树的数量
        // 左子树的根节点为先序遍历的头节点的index+1 递归左子树的左边界还是in_left 递归右子树的右边界是中序的根节点索引-1
        root.left = recur(pre_root+1, in_left, inorderIndex-1);
        root.right = recur(pre_root+(inorderIndex-in_left)+1, inorderIndex+1, in_right);
        return root;
    }
}
